package a04_字符串;

import java.util.Arrays;

/**
 * <p>
 * a06_实现strStr
 * kmp算法
 * aabaabaaf
 * aabaaf
 * 发现aabaaf和aabaab不匹配直接跳到了aab的b之后开始匹配
 *
 * aabaaf的前缀
 * a
 * aa
 * aab
 * aaba
 * aabaa
 *
 * aabaaf的后缀
 * f
 * af
 * aaf
 * baaf
 * abaaf
 *
 * 求最长相等前后缀
 * a   0
 * aa  1
 * aab 0
 * aaba 1
 * aabaa 2
 * aabaaf 0
 *
 * aabaaf的前缀表就是
 * 010120
 *
 * 开始比较
 * aabaabaaf
 * aabaaf
 * 010120
 *
 * 发现f不匹配
 * 前面子串的最长相等前后缀为2
 * 说明这里有一个aa，前面也有一个aa
 * 我们在后面的aa的后面的f不匹配了
 * 我们就得从前面的aa后面的b开始匹配，下标刚好就是2
 *
 * 此时这样开始匹配
 * aabaabaaf
 * aa   baaf
 * </p>
 *
 * @author flyduck
 * @since 2024-07-11
 */
public class a06_实现strStr {

    //aabaabaaf
    //aabaaf

    //hello
    //ll
    public static void main(String[] args) {

//        System.out.println(strStr("aabaabaaf", "aabaaf"));
//        System.out.println(strStr("hello", "ll"));
//        System.out.println(strStr("leetcode", "leeto"));
        System.out.println(strStr("a", "a"));

//        String str = "abbaabaaf";
//        int[] nextArray = new int[str.length()];
//        getNext(nextArray,str);
//        System.out.println(Arrays.toString(str.toCharArray()));
//        System.out.println(Arrays.toString(nextArray));
    }

    public static int strStr(String longStr, String shortStr) {
        int[] nextArray = new int[shortStr.length()];
        getNext(nextArray, shortStr);

        char[] longArray = longStr.toCharArray();
        char[] shortArray = shortStr.toCharArray();
        int longIdx = 0;
        int shortIdx = 0;
        while (shortIdx < shortArray.length && longIdx < longArray.length) {
            if(longArray[longIdx] == shortArray[shortIdx]){
                longIdx++;
                shortIdx++;
            }else {
                if(nextArray[shortIdx] == -1){//相当于用短数组的第一个和longIdx对比失败了，那么longIdx就得++了
                    longIdx++;
                }else {
                    shortIdx = nextArray[shortIdx];
                }

            }
        }
        if(shortIdx == shortArray.length){
            return longIdx - shortIdx;
        }else {
            return -1;
        }

    }


    //leftLastIndex:指向前缀末尾位置(i之前(包括i)子串的最长相等前后缀长度)
    //rightLastIndex:指向后缀末尾位置
    //[a,  b, b, a, a, b, a, a, f]
    //[-1, 0, 0, 0, 1, 1, 2, 1, 1]
    public static void getNext(int[] nextArray,String str){
        if(str.length() == 1){
            nextArray[0] = -1;
            return;
        }
        //1、初始化 第一个肯定是-1，第二个肯定是0
        nextArray[0] = -1;
        nextArray[1] = 0;
        char[] chars = str.toCharArray();

        int currentIndex = 2;//当前要计算得索引
        int compareIndex = nextArray[currentIndex-1];//要比较的索引

        while (currentIndex < chars.length){//终止条件：currentIndex不能超过数组的长度
            if(chars[currentIndex-1] == chars[compareIndex]){//如果前一个元素和比较的元素相等
                nextArray[currentIndex] = compareIndex + 1;//那么当前的应该赋值为
                currentIndex++;//下一个元素
                compareIndex = nextArray[currentIndex-1];//重新设置要比较的索引
            }else {//如果不相等
                if(nextArray[compareIndex] == -1){//如果要比较的元素已经是第一个元素了，并且还不相等，直接设置为0
                    nextArray[currentIndex] = 0;
                    currentIndex++;
                    compareIndex = nextArray[currentIndex-1];
                }else {//如果不是第一个元素，继续往前跳跃
                    compareIndex = nextArray[compareIndex];
                }
            }
        }
    }


}
